/*
 * @lc app=leetcode.cn id=143 lang=typescript
 *
 * [143] 重排链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    let mid = getMidNode(head);
    let l1 = head;
    let l2 = mid.next;
    mid.next = null;
    l2 = reverseList(l2);
    mergeList(l1, l2)
};

const reverseList = (head) => {
    let prev = null;
    let cur = head;
    while (cur) {
        let next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

const mergeList = (l1, l2) => {
    let temp_1 = null;
    let temp_2 = null;
    while (l1 !== null && l2 !== null) {
        temp_1 = l1.next;
        temp_2 = l2.next;

        l1.next = l2;
        l1 = temp_1;

        l2.next = l1;
        l2 = temp_2;
    }
}

const getMidNode = (head) => {
    let fast = head;
    let low = head;
    while (fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next
        low = low.next;
    }
    return low;
}
// @lc code=end

